class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        match = {'(':')', '[':']', '{':'}'}
        t = []
        for c in s:
            if c in ['(', '[', '{']:
                t.append(c)
            else:
                if len(t)!=0 and match[t[-1]]==c:
                    t.pop()
                else:
                    return False
        return len(t)==0

print(Solution().isValid('()')) 